package basis.netease.medium;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Scanner;

/**
 * 7-17 按格式重排链表
 * 给定一个单链表L1→L2→⋯→Ln−1→Ln
 * 请编写程序将链表重新排列为Ln→L1→Ln−1→L2→…
 * 例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3
 * 输入格式：
 * 第一行包含头节点地址，总节点数量 N （1≤N≤100000）
 * 节点地址用一个 5 位非负整数表示（可能有前导 0），空地址 NULL 用 −1 表示。
 * 接下来 N 行，每行描述一个节点的信息，格式如下：
 * Address Data Next
 * 其中 Address 是节点地址，Data 是一个绝对值不超过100000的整数，Next 是下一个节点的地址。
 * 题目保证给出的链表上至少有两个结点。
 * 输出格式：
 * 对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。
 * 输入样例:
 * 在这里给出一组输入。例如：
 * 00100 6
 * 00000 4 99999
 * 00100 1 12309
 * 68237 6 -1
 * 33218 3 00000
 * 99999 5 68237
 * 12309 2 33218
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * 68237 6 00100
 * 00100 1 99999
 * 99999 5 12309
 * 12309 2 00000
 * 00000 4 33218
 * 33218 3 -1
 */
public class Main_14 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] params = in.nextLine().split(" ");
        String rootAddress = params[0];
        int n = Integer.parseInt(params[1]);
        Map<String, Node> nodeMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String[] lineArr = in.nextLine().split(" ");
            nodeMap.put(lineArr[0], new Node(lineArr[0], lineArr[1], lineArr[2]));
        }
        LinkedList<Node> nodeList = new LinkedList();
        Node node = nodeMap.get(rootAddress);
        while (node != null) {
            nodeList.add(node);
            node = nodeMap.get(node.next);
        }
        Node[] nodeArray = new Node[nodeList.size()];
        for (int i = 0; i < nodeArray.length; ) {
            Node lastNode = nodeList.pollLast();
            nodeArray[i] = lastNode;
            i++;
            Node firstNode = nodeList.pollFirst();
            if (firstNode != null) {
                nodeArray[i] = firstNode;
                i++;
            }
        }
        for (int i = 0; i < nodeArray.length; i++) {
            Node current = nodeArray[i];
            if (i + 1 < nodeArray.length) {
                Node next = nodeArray[i + 1];
                System.out.println(current.address + " " + current.data + " " + next.address);
                continue;
            }
            System.out.println(current.address + " " + current.data + " -1");
        }
    }

    static class Node {
        String address;
        String data;
        String next;

        Node(String address, String data, String next) {
            this.address = address;
            this.data = data;
            this.next = next;
        }

        public String toString() {
            return address + " " + data + " " + next;
        }
    }
}
